Equivalence classes.html (2391B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.0.3 (456341)"/><meta name="keywords" content="sets"/><meta name="altitude" content="-0.3668020665645599"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-02-27 14:56:56 +0000"/><meta name="latitude" content="52.33328100117655"/><meta name="longitude" content="4.86550032171256"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-02-27 15:38:50 +0000"/><title>Equivalence classes</title></head><body style="zoom: 1;"><div>a <span style="font-style: italic;">binary </span>relation R is an equivalence relation if for all elements x, y, z in its domain, R satisfies:</div><div><ul><li>reflexivity: x R x</li><li>symmetry: x R y ➝ y R x</li><li>transitivity: x R y ∧ y R z ➝ x R z</li></ul><div><br/></div></div><div><span style="font-weight: bold;">Equivalence classes</span></div><div>an equivalence class consists of all elements x,y for which x R y</div><div>within an equivalence class, all formulas are semantically equivalent</div><div>each equivalence class contains infinitely many formulas</div><div>one class contains all tautologies, another all contradictions (all semantically equivalent)</div><div>for two vars p,q there are as many ≡-equivalence classes as truth tables for p,q — i.e. 16</div><div><br/></div><div><span style="text-decoration: underline;">how many equivalence classes?</span></div><div>for one variable p, there are two valuations (T or F)</div><div>each valuation has two possible outcomes (T or F)</div><div>therefore, 2<span style="vertical-align: super;">2</span> = 4 equivalence classes</div><div><br/></div><div>for two variables p,q there are four valuations (T or F for each var)</div><div>each valuation has two possible outcomes (T or F)</div><div>therefore, 2<span style="vertical-align: super;">4</span> = 16 equivalence classes</div><div>etc. for n variables, there are 2<span style="vertical-align: super;">n</span> valuations and 2<span style="vertical-align: super;">2^n</span> equivalence classes.</div></body></html>